package com.c2b.algorithm.leetcode.base;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href='https://leetcode.cn/problems/frequency-tracker/'>频率跟踪器(Frequency Tracker)</a>
 * <p>请你设计并实现一个能够对其中的值进行跟踪的数据结构，并支持对频率相关查询进行应答。</p>
 * <p>
 * 实现 FrequencyTracker 类：
 *     <ul>
 *         <li>FrequencyTracker()：使用一个空数组初始化 FrequencyTracker 对象。</li>
 *         <li>void add(int number)：添加一个 number 到数据结构中。</li>
 *         <li>void deleteOne(int number)：从数据结构中删除一个 number 。数据结构 可能不包含 number ，在这种情况下不删除任何内容。</li>
 *         <li>bool hasFrequency(int frequency): 如果数据结构中存在出现 frequency 次的数字，则返回 true，否则返回 false。</li>
 *     </ul>
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入
 *          ["FrequencyTracker", "add", "add", "hasFrequency"]
 *          [[], [3], [3], [2]]
 *      输出
 *          [null, null, null, true]
 *      解释
 *          FrequencyTracker frequencyTracker = new FrequencyTracker();
 *          frequencyTracker.add(3); // 数据结构现在包含 [3]
 *          frequencyTracker.add(3); // 数据结构现在包含 [3, 3]
 *          frequencyTracker.hasFrequency(2); // 返回 true ，因为 3 出现 2 次
 *
 * 示例 2：
 *      输入
 *          ["FrequencyTracker", "add", "deleteOne", "hasFrequency"]
 *          [[], [1], [1], [1]]
 *      输出
 *          [null, null, null, false]
 *      解释
 *          FrequencyTracker frequencyTracker = new FrequencyTracker();
 *          frequencyTracker.add(1); // 数据结构现在包含 [1]
 *          frequencyTracker.deleteOne(1); // 数据结构现在为空 []
 *          frequencyTracker.hasFrequency(1); // 返回 false ，因为数据结构为空
 *
 * 示例 3：
 *      输入
 *          ["FrequencyTracker", "hasFrequency", "add", "hasFrequency"]
 *          [[], [2], [3], [1]]
 *      输出
 *          [null, false, null, true]
 *      解释
 *          FrequencyTracker frequencyTracker = new FrequencyTracker();
 *          frequencyTracker.hasFrequency(2); // 返回 false ，因为数据结构为空
 *          frequencyTracker.add(3); // 数据结构现在包含 [3]
 *          frequencyTracker.hasFrequency(1); // 返回 true ，因为 3 出现 1 次
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= number <= 10^5</li>
 *     <li>1 <= frequency <= 10^5</li>
 *     <li>最多调用 add、deleteOne 和 hasFrequency 共计 2 * 10^5 次</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/3/21 9:22
 */
public class LC2671FrequencyTracker_M {
    static class FrequencyTracker {
        //private static final int N = 100001;
        //// 用于记录当前值出现的次数
        //int[] values;
        //// 用于记录出现当前次数的值的个数
        //int[] frequencies;

        private final Map<Integer, Integer> value2frequencyMap;
        private final Map<Integer, Integer> frequencyMap;

        public FrequencyTracker() {
            value2frequencyMap = new HashMap<>();
            frequencyMap = new HashMap<>();
            //values = new int[N];
            //frequencies = new int[N];
        }

        public void add(int number) {
            Integer frequency = value2frequencyMap.getOrDefault(number, 0);
            value2frequencyMap.put(number, frequency + 1);
            if (frequency != 0) {
                // 从旧的频次列表中删除，并添加到新的频次列表中
                frequencyMap.put(frequency, frequencyMap.getOrDefault(frequency, 0) - 1);
            }
            frequencyMap.put(frequency + 1, frequencyMap.getOrDefault(frequency + 1, 0) + 1);

            //--frequencies[values[number]];
            //++values[number];
            //++frequencies[values[number]];
        }

        public void deleteOne(int number) {
            int frequency = value2frequencyMap.getOrDefault(number, 0);
            if (frequency == 0) {
                return;
            }
            value2frequencyMap.put(number, frequency - 1);
            frequencyMap.put(frequency, frequencyMap.get(frequency) - 1);
            frequencyMap.put(frequency - 1, frequencyMap.getOrDefault(frequency - 1, 0) + 1);

            //if (values[number] == 0) {
            //    return;
            //}
            //--frequencies[values[number]];
            //--values[number];
            //++frequencies[values[number]];
        }

        public boolean hasFrequency(int frequency) {
            return frequencyMap.getOrDefault(frequency, 0) > 0;
            //return frequencies[frequency] > 0;
        }
    }

    public static void main(String[] args) {
        //FrequencyTracker frequencyTracker1 = new FrequencyTracker();
        //frequencyTracker1.add(3);
        //frequencyTracker1.add(3);
        //System.out.println(frequencyTracker1.hasFrequency(2));
        //System.out.println("========");
        //
        //FrequencyTracker frequencyTracker2 = new FrequencyTracker();
        //frequencyTracker2.add(1);
        //frequencyTracker2.deleteOne(1);
        //System.out.println(frequencyTracker2.hasFrequency(1));
        //System.out.println("========");
        //
        //FrequencyTracker frequencyTracker3 = new FrequencyTracker();
        //System.out.println(frequencyTracker3.hasFrequency(2));
        //frequencyTracker3.add(3);
        //System.out.println(frequencyTracker3.hasFrequency(1));
        //System.out.println("========");

        FrequencyTracker tracker = new FrequencyTracker();
        tracker.deleteOne(9);
        tracker.deleteOne(8);
        tracker.deleteOne(1);
        tracker.deleteOne(4);

        System.out.println(tracker.hasFrequency(1));
        tracker.add(10);
        tracker.deleteOne(5);
        System.out.println(tracker.hasFrequency(1));

        tracker.deleteOne(10);
        tracker.deleteOne(9);
        tracker.deleteOne(10);
        System.out.println(tracker.hasFrequency(1));

        tracker.add(4);
        System.out.println(tracker.hasFrequency(1));
        tracker.deleteOne(4);
        System.out.println(tracker.hasFrequency(1));

        System.out.println(tracker.hasFrequency(1));
        tracker.add(10);
        System.out.println(tracker.hasFrequency(1));
        tracker.add(2);

        tracker.deleteOne(1);
        System.out.println(tracker.hasFrequency(2));
        tracker.add(7);
        System.out.println(tracker.hasFrequency(1));
        System.out.println(tracker.hasFrequency(1));
        tracker.add(6);
    }
}
